LeetCode 695、岛屿的最大面积

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 矩阵的行数
        m = len(grid)

        # 矩阵的列数
        n = len(grid[0])

        maxx = 0

        # 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
        # 特殊的单元格：必然是从边界处开始的
        for  i in range(0 , m ) : 

            for j in range( 0 , n ):

                if(grid[i][j] == 1):

                    area = self.dfs(grid,i,j)

                    maxx = max(maxx,area)

        return maxx
   

    def dfs(self, grid: List[List[str]], i : int , j : int ) -> int:
        # dfs搜索、递归终止条件
        # i < 0 ，越界
        # j < 0 ，越界
        # i >= board.length ，越界
        # j >= board[0].length ，越界
        # board[i][j] == X ，不需要继续搜索下去
        # board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
        if  i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0])  or grid[i][j] == 0 : 
            return 0
            
        
        # 将当前单元格置为 0 ，避免其它格子 dfs 过程中又把它加入到计算中
        grid[i][j] = 0

        res = 1 
        # 在当前单元格的四个方向开始搜索
        # 上：（ 0 ， -1 ）
        # 下：（ 0 ， 1 ）
        # 左：（ -1 ， 0 ）
        # 右：（ 1 ， 0 ）
        # 朝着这四个方向开始延伸搜索下去
        for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):

            # 下一个即将去搜索网格的横坐标
            next_i = i + dx

            # 下一个即将去搜索网格的纵坐标
            next_j = j + dy

            area = self.dfs(grid,next_i,next_j)

            res += area
        
        return res

四、复杂度分析

时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。

空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。